// @algorithm @lc id=494 lang=cpp 
// @title target-sum

#define print(...)
// @test([1,1,1,1,1],3)=5
// @test([1],1)=1
class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        print("\nnums=", nums, "\n")
        int sum = accumulate(nums.begin(), nums.end(), 0);
        print("sum:", sum, "\n")
        int neg = sum - target;
        if(neg<0 || neg%2) return 0;
        neg >>= 1;
        print("neg:", neg, "\n")
        unordered_map<int, int> dp;
        dp[0] = 1;
        for(auto & a : nums){
            for(int t=neg; t>=a; t--)
                dp[t] += dp[t-a];
        }
        print("dp:", dp, "\n")
        return dp[neg];
    }
};